/*-------------------------------------------------------------------------
 *
 * freepage.c
 *	  空闲内存页面管理。
 *
 * 此代码的目的是为专门为 PostgreSQL 编写的内存分配器提供基础设施。
 * 至少在动态共享内存的情况下，我们不能简单地使用 malloc()，甚至不能使用像 palloc() 这样的相对薄的包装，因为没有操作系统内置的分配器会处理相对指针。
 * 将来，我们可能会发现其他需要对我们自己的内存管理进行更严格控制的情况。
 *
 * 一个 FreePageManager 跟踪从某个高级内存分配器的角度当前未使用的 4KB 内存页面。与 palloc() 等用户面对的分配器不同，FreePageManager 只能按整体页面单位分配和释放，而且释放分配时只能在已知其长度为页面的情况下进行。
 *
 * 由于空闲页面管理器只有固定数量的专用内存，并且没有底层分配器，它使用自其管理的空闲页面来存储其书面数据。它保持多个空闲页面的运行列表，按运行大小排序；每个空闲列表的头部存储在 FreePageManager 本身中，并且每个运行的第一页包含对下一个运行的相对指针。有关空闲列表管理的更多详细信息，请参见 FreePageManagerGetInternal。
 *
 * 为了避免内存碎片，合并相邻页面的跨度非常重要；否则，即使有足够的连续空间，较大的分配请求也可能无法满足。因此，除了空闲列表，我们维持了一个内存中的自由页面范围的 btree，按页面编号排序。如果要释放的范围在已经空闲的范围之前或之后，现有的范围会被扩展；如果它正好跨越空闲范围之间的间隔，则将两个现有范围与新释放的范围合并，以形成一个更大的空闲页面范围。
 *
 * 当只有一个空闲页面范围时，btree 是微不足道的，并存储在 FreePageManager 中；否则，在需要时从管理区域中分配页面。即使在内存碎片非常严重的情况下，管理内容下的页面被此 btree 消耗的比例也很小。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/utils/mmgr/freepage.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"
#include "lib/stringinfo.h"
#include "miscadmin.h"

#include "utils/freepage.h"
#include "utils/relptr.h"


/* 用于识别各种页类型的魔术数字 */
#define FREE_PAGE_SPAN_LEADER_MAGIC		0xea4020f0
#define FREE_PAGE_LEAF_MAGIC			0x98eae728
#define FREE_PAGE_INTERNAL_MAGIC		0x19aa32c9

/* 自由页面的跨度的双向链表；存储在跨度的第一页中。 */
struct FreePageSpanLeader
{
	int			magic;			/* 始终为 FREE_PAGE_SPAN_LEADER_MAGIC */
	Size		npages;			/* 跨度中的页数 */
	RelptrFreePageSpanLeader prev;
	RelptrFreePageSpanLeader next;
};

/* btree 叶子页和内部页的公共头部。 */
typedef struct FreePageBtreeHeader
{
	int			magic;			/* FREE_PAGE_LEAF_MAGIC 或
								 * FREE_PAGE_INTERNAL_MAGIC */
	Size		nused;			/* 使用的项目数量 */
	RelptrFreePageBtree parent; /* uplink */
} FreePageBtreeHeader;

/* 内部键；点到 btree 的下一层。 */
typedef struct FreePageBtreeInternalKey
{
	Size		first_page;		/* 子页上键的下限 */
	RelptrFreePageBtree child;	/* downlink */
} FreePageBtreeInternalKey;

/* 叶子键；没有有效负载数据。 */
typedef struct FreePageBtreeLeafKey
{
	Size		first_page;		/* 跨度中的第一页 */
	Size		npages;			/* 跨度中的页数 */
} FreePageBtreeLeafKey;

/* 计算每页可以容纳多少个键。 */
#define FPM_ITEMS_PER_INTERNAL_PAGE \
	((FPM_PAGE_SIZE - sizeof(FreePageBtreeHeader)) / \
		sizeof(FreePageBtreeInternalKey))
#define FPM_ITEMS_PER_LEAF_PAGE \
	((FPM_PAGE_SIZE - sizeof(FreePageBtreeHeader)) / \
		sizeof(FreePageBtreeLeafKey))

/* 一个B树页面，可以是任何一种 */
struct FreePageBtree
{
	FreePageBtreeHeader hdr;
	union
	{
		FreePageBtreeInternalKey internal_key[FPM_ITEMS_PER_INTERNAL_PAGE];
		FreePageBtreeLeafKey leaf_key[FPM_ITEMS_PER_LEAF_PAGE];
	}			u;
};

/* B树搜索的结果 */
typedef struct FreePageBtreeSearchResult
{
	FreePageBtree *page;
	Size		index;
	bool		found;
	unsigned	split_pages;
} FreePageBtreeSearchResult;

/* 辅助函数 */
static void fc_FreePageBtreeAdjustAncestorKeys(FreePageManager *fc_fpm,
											FreePageBtree *fc_btp);
static Size fc_FreePageBtreeCleanup(FreePageManager *fc_fpm);
static FreePageBtree *fc_FreePageBtreeFindLeftSibling(char *fc_base,
												   FreePageBtree *fc_btp);
static FreePageBtree *fc_FreePageBtreeFindRightSibling(char *fc_base,
													FreePageBtree *fc_btp);
static Size fc_FreePageBtreeFirstKey(FreePageBtree *fc_btp);
static FreePageBtree *fc_FreePageBtreeGetRecycled(FreePageManager *fc_fpm);
static void fc_FreePageBtreeInsertInternal(char *fc_base, FreePageBtree *fc_btp,
										Size fc_index, Size fc_first_page, FreePageBtree *fc_child);
static void fc_FreePageBtreeInsertLeaf(FreePageBtree *fc_btp, Size fc_index,
									Size fc_first_page, Size fc_npages);
static void fc_FreePageBtreeRecycle(FreePageManager *fc_fpm, Size fc_pageno);
static void fc_FreePageBtreeRemove(FreePageManager *fc_fpm, FreePageBtree *fc_btp,
								Size fc_index);
static void fc_FreePageBtreeRemovePage(FreePageManager *fc_fpm, FreePageBtree *fc_btp);
static void fc_FreePageBtreeSearch(FreePageManager *fc_fpm, Size fc_first_page,
								FreePageBtreeSearchResult *fc_result);
static Size fc_FreePageBtreeSearchInternal(FreePageBtree *fc_btp, Size fc_first_page);
static Size fc_FreePageBtreeSearchLeaf(FreePageBtree *fc_btp, Size fc_first_page);
static FreePageBtree *fc_FreePageBtreeSplitPage(FreePageManager *fc_fpm,
											 FreePageBtree *fc_btp);
static void fc_FreePageBtreeUpdateParentPointers(char *fc_base, FreePageBtree *fc_btp);
static void fc_FreePageManagerDumpBtree(FreePageManager *fc_fpm, FreePageBtree *fc_btp,
									 FreePageBtree *fc_parent, int fc_level, StringInfo fc_buf);
static void fc_FreePageManagerDumpSpans(FreePageManager *fc_fpm,
									 FreePageSpanLeader *fc_span, Size fc_expected_pages,
									 StringInfo fc_buf);
static bool fc_FreePageManagerGetInternal(FreePageManager *fc_fpm, Size fc_npages,
									   Size *fc_first_page);
static Size fc_FreePageManagerPutInternal(FreePageManager *fc_fpm, Size fc_first_page,
									   Size fc_npages, bool fc_soft);
static void fc_FreePagePopSpanLeader(FreePageManager *fc_fpm, Size fc_pageno);
static void fc_FreePagePushSpanLeader(FreePageManager *fc_fpm, Size fc_first_page,
								   Size fc_npages);
static Size fc_FreePageManagerLargestContiguous(FreePageManager *fc_fpm);
static void fc_FreePageManagerUpdateLargest(FreePageManager *fc_fpm);

#ifdef FPM_EXTRA_ASSERTS
static Size fc_sum_free_pages(FreePageManager *fc_fpm);
#endif

/*
 * 初始化一个新的、空的空闲页面管理器。
 *
 * 'fpm' 应该引用调用者提供的内存，该内存足够大以容纳一个
 * FreePageManager。我们将在此处初始化它。
 *
 * 'base' 是所有指针相对的地址。当管理一个动态共享内存段时，
 * 通常应该是该段的基地址。当管理后端私有内存时，它可以是 NULL，
 * 或者如果管理一个连续的内存区段，则是该区段的起始地址。
 */
void FreePageManagerInitialize(FreePageManager *fc_fpm, char *fc_base)
{
	Size		fc_f;

	relptr_store(fc_base, fc_fpm->self, fc_fpm);
	relptr_store(fc_base, fc_fpm->btree_root, (FreePageBtree *) NULL);
	relptr_store(fc_base, fc_fpm->btree_recycle, (FreePageSpanLeader *) NULL);
	fc_fpm->btree_depth = 0;
	fc_fpm->btree_recycle_count = 0;
	fc_fpm->singleton_first_page = 0;
	fc_fpm->singleton_npages = 0;
	fc_fpm->contiguous_pages = 0;
	fc_fpm->contiguous_pages_dirty = true;
#ifdef FPM_EXTRA_ASSERTS
	fc_fpm->free_pages = 0;
#endif

	for (fc_f = 0; fc_f < FPM_NUM_FREELISTS; fc_f++)
		relptr_store(fc_base, fc_fpm->freelist[fc_f], (FreePageSpanLeader *) NULL);
}

/*
 * 从空闲页面管理器中分配给定长度的一组页面。
 * 返回值指示我们是否能够满足请求；如果为真，
 * 分配的第一页面存储在 *first_page 中。
 */
bool FreePageManagerGet(FreePageManager *fc_fpm, Size fc_npages, Size *fc_first_page)
{
	bool		fc_result;
	Size		fc_contiguous_pages;

	fc_result = fc_FreePageManagerGetInternal(fc_fpm, fc_npages, fc_first_page);

	/*
	 * 这有点违反直觉，但分配页面实际上可以创造出清理的机会，
	 * 扩大范围。我们可能会从B树中提取一个键，使得可以插入
	 * 在B树回收列表头部的项；然后如果在它后面还有更多项，
	 * 其中一个可能会导致两个当前分开的范围合并，
	 * 创建一个单一的比以前存在的连续页面范围更大的范围。
	 * 改进清理算法以避免这种边界情况可能值得一试，
	 * 但现在我们只是注意到这种情况并进行适当的报告。
	 */
	fc_contiguous_pages = fc_FreePageBtreeCleanup(fc_fpm);
	if (fc_fpm->contiguous_pages < fc_contiguous_pages)
		fc_fpm->contiguous_pages = fc_contiguous_pages;

	/*
	 * FreePageManagerGetInternal 可能已设置 contiguous_pages_dirty。
	 * 如果是这样，请重新计算 contiguous_pages。
	 */
	fc_FreePageManagerUpdateLargest(fc_fpm);

#ifdef FPM_EXTRA_ASSERTS
	if (fc_result)
	{
		Assert(fc_fpm->free_pages >= fc_npages);
		fc_fpm->free_pages -= fc_npages;
	}
	Assert(fc_fpm->free_pages == fc_sum_free_pages(fc_fpm));
	Assert(fc_fpm->contiguous_pages == fc_FreePageManagerLargestContiguous(fc_fpm));
#endif
	return fc_result;
}

#ifdef FPM_EXTRA_ASSERTS
static void fc_sum_free_pages_recurse(FreePageManager *fc_fpm, FreePageBtree *fc_btp, Size *fc_sum)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);

	Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC ||
		   fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC);
	++*fc_sum;
	if (fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC)
	{
		Size		fc_index;


		for (fc_index = 0; fc_index < fc_btp->hdr.nused; ++fc_index)
		{
			FreePageBtree *fc_child;

			fc_child = relptr_access(fc_base, fc_btp->u.internal_key[fc_index].child);
			fc_sum_free_pages_recurse(fc_fpm, fc_child, fc_sum);
		}
	}
}
static Size fc_sum_free_pages(FreePageManager *fc_fpm)
{
	FreePageSpanLeader *fc_recycle;
	char	   *fc_base = fpm_segment_base(fc_fpm);
	Size		fc_sum = 0;
	int			fc_list;

	/* 通过扫描空闲列表来计算跨度。 */
	for (fc_list = 0; fc_list < FPM_NUM_FREELISTS; ++fc_list)
	{

		if (!relptr_is_null(fc_fpm->freelist[fc_list]))
		{
			FreePageSpanLeader *fc_candidate =
			relptr_access(fc_base, fc_fpm->freelist[fc_list]);

			do
			{
				fc_sum += fc_candidate->npages;
				fc_candidate = relptr_access(fc_base, fc_candidate->next);
			} while (fc_candidate != NULL);
		}
	}

	/* 计算B树内部页面。 */
	if (fc_fpm->btree_depth > 0)
	{
		FreePageBtree *fc_root = relptr_access(fc_base, fc_fpm->btree_root);

		fc_sum_free_pages_recurse(fc_fpm, fc_root, &fc_sum);
	}

	/* 计算回收列表。 */
	for (fc_recycle = relptr_access(fc_base, fc_fpm->btree_recycle);
		 fc_recycle != NULL;
		 fc_recycle = relptr_access(fc_base, fc_recycle->next))
	{
		Assert(fc_recycle->npages == 1);
		++fc_sum;
	}

	return fc_sum;
}
#endif

/*
 * 计算用户可以成功获取的最大连续页面的大小。
 */
static Size fc_FreePageManagerLargestContiguous(FreePageManager *fc_fpm)
{
	char	   *fc_base;
	Size		fc_largest;

	fc_base = fpm_segment_base(fc_fpm);
	fc_largest = 0;
	if (!relptr_is_null(fc_fpm->freelist[FPM_NUM_FREELISTS - 1]))
	{
		FreePageSpanLeader *fc_candidate;

		fc_candidate = relptr_access(fc_base, fc_fpm->freelist[FPM_NUM_FREELISTS - 1]);
		do
		{
			if (fc_candidate->npages > fc_largest)
				fc_largest = fc_candidate->npages;
			fc_candidate = relptr_access(fc_base, fc_candidate->next);
		} while (fc_candidate != NULL);
	}
	else
	{
		Size		fc_f = FPM_NUM_FREELISTS - 1;

		do
		{
			--fc_f;
			if (!relptr_is_null(fc_fpm->freelist[fc_f]))
			{
				fc_largest = fc_f + 1;
				break;
			}
		} while (fc_f > 0);
	}

	return fc_largest;
}

/*
 * 如果被标记为脏，则重新计算用户可以成功获取的最大连续页面的大小。
 */
static void fc_FreePageManagerUpdateLargest(FreePageManager *fc_fpm)
{
	if (!fc_fpm->contiguous_pages_dirty)
		return;

	fc_fpm->contiguous_pages = fc_FreePageManagerLargestContiguous(fc_fpm);
	fc_fpm->contiguous_pages_dirty = false;
}

/*
 * 将一组页面转移到空闲页面管理器中。
 */
void FreePageManagerPut(FreePageManager *fc_fpm, Size fc_first_page, Size fc_npages)
{
	Size		fc_contiguous_pages;

	Assert(fc_npages > 0);

	/* 记录新页面。 */
	fc_contiguous_pages =
		fc_FreePageManagerPutInternal(fc_fpm, fc_first_page, fc_npages, false);

	/*
	 * 如果我们插入页面管理器的新范围与现有范围是连续的，
	 * 则可能打开了清理机会。
	 */
	if (fc_contiguous_pages > fc_npages)
	{
		Size		fc_cleanup_contiguous_pages;

		fc_cleanup_contiguous_pages = fc_FreePageBtreeCleanup(fc_fpm);
		if (fc_cleanup_contiguous_pages > fc_contiguous_pages)
			fc_contiguous_pages = fc_cleanup_contiguous_pages;
	}

	/* 看看我们现在是否有一个新的最大块。 */
	if (fc_fpm->contiguous_pages < fc_contiguous_pages)
		fc_fpm->contiguous_pages = fc_contiguous_pages;

	/*
	 * 之前对 FreePageManagerPutInternal 的调用可能已设置
	 * contiguous_pages_dirty（如果需要分配内部页面），因此
	 * 有必要时重新计算 contiguous_pages。
	 */
	fc_FreePageManagerUpdateLargest(fc_fpm);

#ifdef FPM_EXTRA_ASSERTS
	fc_fpm->free_pages += fc_npages;
	Assert(fc_fpm->free_pages == fc_sum_free_pages(fc_fpm));
	Assert(fc_fpm->contiguous_pages == fc_FreePageManagerLargestContiguous(fc_fpm));
#endif
}

/*
 * 生成空闲页面管理器状态的调试转储。
 */
char * FreePageManagerDump(FreePageManager *fc_fpm)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	StringInfoData fc_buf;
	FreePageSpanLeader *fc_recycle;
	bool		fc_dumped_any_freelist = false;
	Size		fc_f;

	/* 初始化输出缓冲区。 */
	initStringInfo(&fc_buf);

	/* 转储常规信息。 */
	appendStringInfo(&fc_buf, "metadata: self %zu max contiguous pages = %zu\n",
					 relptr_offset(fc_fpm->self), fc_fpm->contiguous_pages);

	/* 转储B树。 */
	if (fc_fpm->btree_depth > 0)
	{
		FreePageBtree *fc_root;

		appendStringInfo(&fc_buf, "btree depth %u:\n", fc_fpm->btree_depth);
		fc_root = relptr_access(fc_base, fc_fpm->btree_root);
		fc_FreePageManagerDumpBtree(fc_fpm, fc_root, NULL, 0, &fc_buf);
	}
	else if (fc_fpm->singleton_npages > 0)
	{
		appendStringInfo(&fc_buf, "singleton: %zu(%zu)\n",
						 fc_fpm->singleton_first_page, fc_fpm->singleton_npages);
	}

	/* 转储B树回收列表。 */
	fc_recycle = relptr_access(fc_base, fc_fpm->btree_recycle);
	if (fc_recycle != NULL)
	{
		appendStringInfoString(&fc_buf, "btree recycle:");
		fc_FreePageManagerDumpSpans(fc_fpm, fc_recycle, 1, &fc_buf);
	}

	/* 转储空闲列表。 */
	for (fc_f = 0; fc_f < FPM_NUM_FREELISTS; ++fc_f)
	{
		FreePageSpanLeader *fc_span;

		if (relptr_is_null(fc_fpm->freelist[fc_f]))
			continue;
		if (!fc_dumped_any_freelist)
		{
			appendStringInfoString(&fc_buf, "freelists:\n");
			fc_dumped_any_freelist = true;
		}
		appendStringInfo(&fc_buf, "  %zu:", fc_f + 1);
		fc_span = relptr_access(fc_base, fc_fpm->freelist[fc_f]);
		fc_FreePageManagerDumpSpans(fc_fpm, fc_span, fc_f + 1, &fc_buf);
	}

	/* 并将结果返回给调用者。 */
	return fc_buf.data;
}


/*
 * 存储在任何非根页面的索引零处的 first_page 值必须与
 * 存储在其父级的索引指向该页面的 first_page 值匹配。
 * 因此，当B树页面中索引零处存储的值发生变化时，
 * 我们必须向上遍历树，调整祖先键，直到我们到达一个
 * 该键不再是索引零的祖先。这一函数应该在
 * 更新目标页面上的第一个键后调用；它将根据需要向上传播更改。
 *
 * 我们在这里假设页面上的第一个键没有变化到足以
 * 需要改变其祖先页面上键的顺序。因此，
 * 如果我们在父页面中搜索大于或等于当前页面上第一个键的
 * 第一个键，下行链接到此页面将是搜索返回的确切索引（如果
 * 第一个键减少）或小一（如果第一个键增加）。
 */
static void fc_FreePageBtreeAdjustAncestorKeys(FreePageManager *fc_fpm, FreePageBtree *fc_btp)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	Size		fc_first_page;
	FreePageBtree *fc_parent;
	FreePageBtree *fc_child;

	/* 这可能是一个叶子页面或内部页面。 */
	Assert(fc_btp->hdr.nused > 0);
	if (fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC)
	{
		Assert(fc_btp->hdr.nused <= FPM_ITEMS_PER_LEAF_PAGE);
		fc_first_page = fc_btp->u.leaf_key[0].first_page;
	}
	else
	{
		Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
		Assert(fc_btp->hdr.nused <= FPM_ITEMS_PER_INTERNAL_PAGE);
		fc_first_page = fc_btp->u.internal_key[0].first_page;
	}
	fc_child = fc_btp;

	/* 循环，直到找到一个不需要调整的祖先。 */
	for (;;)
	{
		Size		fc_s;

		fc_parent = relptr_access(fc_base, fc_child->hdr.parent);
		if (fc_parent == NULL)
			break;
		fc_s = fc_FreePageBtreeSearchInternal(fc_parent, fc_first_page);

		/* 键位于索引 s 或索引 s-1；确定是哪一个。 */
		if (fc_s >= fc_parent->hdr.nused)
		{
			Assert(fc_s == fc_parent->hdr.nused);
			--fc_s;
		}
		else
		{
			FreePageBtree *fc_check;

			fc_check = relptr_access(fc_base, fc_parent->u.internal_key[fc_s].child);
			if (fc_check != fc_child)
			{
				Assert(fc_s > 0);
				--fc_s;
			}
		}

#ifdef USE_ASSERT_CHECKING
		/* 调试双重检查。 */
		{
			FreePageBtree *fc_check;

			fc_check = relptr_access(fc_base, fc_parent->u.internal_key[fc_s].child);
			Assert(fc_s < fc_parent->hdr.nused);
			Assert(fc_child == fc_check);
		}
#endif

		/* 更新父键。 */
		fc_parent->u.internal_key[fc_s].first_page = fc_first_page;

		/*
		 * 如果这是父节点中的第一个键，则向上再移一层；否则
		 * 完成。
		 */
		if (fc_s > 0)
			break;
		fc_child = fc_parent;
	}
}

/*
 * 尝试从空闲页的 B 树中回收空间。返回值是
 * 清理操作创建的最大连续页面范围。
 */
static Size fc_FreePageBtreeCleanup(FreePageManager *fc_fpm)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	Size		fc_max_contiguous_pages = 0;

	/* 尝试缩小 B 树的深度。 */
	while (!relptr_is_null(fc_fpm->btree_root))
	{
		FreePageBtree *fc_root = relptr_access(fc_base, fc_fpm->btree_root);

		/* 如果根节点只包含一个键，则深度减少一个。 */
		if (fc_root->hdr.nused == 1)
		{
			/* 将树的深度缩小一个。 */
			Assert(fc_fpm->btree_depth > 0);
			--fc_fpm->btree_depth;
			if (fc_root->hdr.magic == FREE_PAGE_LEAF_MAGIC)
			{
				/* 如果根节点是叶子节点，只将条目转换为单一范围。 */
				relptr_store(fc_base, fc_fpm->btree_root, (FreePageBtree *) NULL);
				fc_fpm->singleton_first_page = fc_root->u.leaf_key[0].first_page;
				fc_fpm->singleton_npages = fc_root->u.leaf_key[0].npages;
			}
			else
			{
				FreePageBtree *fc_newroot;

				/* 如果根节点是内部页面，则使唯一的子节点成为根。 */
				Assert(fc_root->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
				relptr_copy(fc_fpm->btree_root, fc_root->u.internal_key[0].child);
				fc_newroot = relptr_access(fc_base, fc_fpm->btree_root);
				relptr_store(fc_base, fc_newroot->hdr.parent, (FreePageBtree *) NULL);
			}
			fc_FreePageBtreeRecycle(fc_fpm, fpm_pointer_to_page(fc_base, fc_root));
		}
		else if (fc_root->hdr.nused == 2 &&
				 fc_root->hdr.magic == FREE_PAGE_LEAF_MAGIC)
		{
			Size		fc_end_of_first;
			Size		fc_start_of_second;

			fc_end_of_first = fc_root->u.leaf_key[0].first_page +
				fc_root->u.leaf_key[0].npages;
			fc_start_of_second = fc_root->u.leaf_key[1].first_page;

			if (fc_end_of_first + 1 == fc_start_of_second)
			{
				Size		fc_root_page = fpm_pointer_to_page(fc_base, fc_root);

				if (fc_end_of_first == fc_root_page)
				{
					fc_FreePagePopSpanLeader(fc_fpm, fc_root->u.leaf_key[0].first_page);
					fc_FreePagePopSpanLeader(fc_fpm, fc_root->u.leaf_key[1].first_page);
					fc_fpm->singleton_first_page = fc_root->u.leaf_key[0].first_page;
					fc_fpm->singleton_npages = fc_root->u.leaf_key[0].npages +
						fc_root->u.leaf_key[1].npages + 1;
					fc_fpm->btree_depth = 0;
					relptr_store(fc_base, fc_fpm->btree_root,
								 (FreePageBtree *) NULL);
					fc_FreePagePushSpanLeader(fc_fpm, fc_fpm->singleton_first_page,
										   fc_fpm->singleton_npages);
					Assert(fc_max_contiguous_pages == 0);
					fc_max_contiguous_pages = fc_fpm->singleton_npages;
				}
			}

			/* 无论是否成功，现在是时候停止了。 */
			break;
		}
		else
		{
			/* 没有更多的事情可做。停止。 */
			break;
		}
	}

	/*
	 * 尝试释放回收的 B 树页面。如果释放回收页面需要
	 * B 树页面分裂，我们将跳过此操作，因为我们想要回收的页面
	 * 会被分裂所消耗，这将是适得其反的。
	 *
	 * 我们目前也只尝试回收列表中的第一页；可以更加激进，但尚不清楚
	 * 其复杂性是否值得。
	 */
	while (fc_fpm->btree_recycle_count > 0)
	{
		FreePageBtree *fc_btp;
		Size		fc_first_page;
		Size		fc_contiguous_pages;

		fc_btp = fc_FreePageBtreeGetRecycled(fc_fpm);
		fc_first_page = fpm_pointer_to_page(fc_base, fc_btp);
		fc_contiguous_pages = fc_FreePageManagerPutInternal(fc_fpm, fc_first_page, 1, true);
		if (fc_contiguous_pages == 0)
		{
			fc_FreePageBtreeRecycle(fc_fpm, fc_first_page);
			break;
		}
		else
		{
			if (fc_contiguous_pages > fc_max_contiguous_pages)
				fc_max_contiguous_pages = fc_contiguous_pages;
		}
	}

	return fc_max_contiguous_pages;
}

/*
 * 考虑将给定页面与其左边或右边的兄弟页面合并，
 * 如果它相对空闲。
 */
static void fc_FreePageBtreeConsolidate(FreePageManager *fc_fpm, FreePageBtree *fc_btp)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageBtree *fc_np;
	Size		fc_max;

	/*
	 * 我们仅尝试合并少于三分之一满的页面。我们
	 * 可以在这方面更加激进，但这可能会冒着仅为合并而合并，
	 * 结果很快又分开。由于 B 树的大小应该相比于管理空间
	 * 非常小，我们的目标并不是确保它始终占据绝对
	 * 最小数量的页面，而是希望在情况过于严重之前回收页面。
	 */
	if (fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC)
		fc_max = FPM_ITEMS_PER_LEAF_PAGE;
	else
	{
		Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
		fc_max = FPM_ITEMS_PER_INTERNAL_PAGE;
	}
	if (fc_btp->hdr.nused >= fc_max / 3)
		return;

	/*
	 * 如果我们可以将右侧兄弟的键放入此页面，则合并。
	 */
	fc_np = fc_FreePageBtreeFindRightSibling(fc_base, fc_btp);
	if (fc_np != NULL && fc_btp->hdr.nused + fc_np->hdr.nused <= fc_max)
	{
		if (fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC)
		{
			memcpy(&fc_btp->u.leaf_key[fc_btp->hdr.nused], &fc_np->u.leaf_key[0],
				   sizeof(FreePageBtreeLeafKey) * fc_np->hdr.nused);
			fc_btp->hdr.nused += fc_np->hdr.nused;
		}
		else
		{
			memcpy(&fc_btp->u.internal_key[fc_btp->hdr.nused], &fc_np->u.internal_key[0],
				   sizeof(FreePageBtreeInternalKey) * fc_np->hdr.nused);
			fc_btp->hdr.nused += fc_np->hdr.nused;
			fc_FreePageBtreeUpdateParentPointers(fc_base, fc_btp);
		}
		fc_FreePageBtreeRemovePage(fc_fpm, fc_np);
		return;
	}

	/*
	 * 如果我们可以将我们的键放入左侧兄弟的页面，则合并。在
	 * 这种情况下，我们将我们的键移动到另一个页面，而不是反过来，
	 * 以避免调整祖先键。
	 */
	fc_np = fc_FreePageBtreeFindLeftSibling(fc_base, fc_btp);
	if (fc_np != NULL && fc_btp->hdr.nused + fc_np->hdr.nused <= fc_max)
	{
		if (fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC)
		{
			memcpy(&fc_np->u.leaf_key[fc_np->hdr.nused], &fc_btp->u.leaf_key[0],
				   sizeof(FreePageBtreeLeafKey) * fc_btp->hdr.nused);
			fc_np->hdr.nused += fc_btp->hdr.nused;
		}
		else
		{
			memcpy(&fc_np->u.internal_key[fc_np->hdr.nused], &fc_btp->u.internal_key[0],
				   sizeof(FreePageBtreeInternalKey) * fc_btp->hdr.nused);
			fc_np->hdr.nused += fc_btp->hdr.nused;
			fc_FreePageBtreeUpdateParentPointers(fc_base, fc_np);
		}
		fc_FreePageBtreeRemovePage(fc_fpm, fc_btp);
		return;
	}
}

/*
 * 找到传入页面的左兄弟；也就是，同一级别
 * 的树中，其键空间紧接着在我们前面的页面。
 */
static FreePageBtree * fc_FreePageBtreeFindLeftSibling(char *fc_base, FreePageBtree *fc_btp)
{
	FreePageBtree *fc_p = fc_btp;
	int			fc_levels = 0;

	/* 向上移动直到我们能够向左移动。 */
	for (;;)
	{
		Size		fc_first_page;
		Size		fc_index;

		fc_first_page = fc_FreePageBtreeFirstKey(fc_p);
		fc_p = relptr_access(fc_base, fc_p->hdr.parent);

		if (fc_p == NULL)
			return NULL;		/* 我们传入的是最右侧的页面 */

		fc_index = fc_FreePageBtreeSearchInternal(fc_p, fc_first_page);
		if (fc_index > 0)
		{
			Assert(fc_p->u.internal_key[fc_index].first_page == fc_first_page);
			fc_p = relptr_access(fc_base, fc_p->u.internal_key[fc_index - 1].child);
			break;
		}
		Assert(fc_index == 0);
		++fc_levels;
	}

	/* 向左下降。 */
	while (fc_levels > 0)
	{
		Assert(fc_p->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
		fc_p = relptr_access(fc_base, fc_p->u.internal_key[fc_p->hdr.nused - 1].child);
		--fc_levels;
	}
	Assert(fc_p->hdr.magic == fc_btp->hdr.magic);

	return fc_p;
}

/*
 * 找到传入页面的右兄弟；也就是，同一级别
 * 的树中，其键空间紧接着在我们后面的页面。
 */
static FreePageBtree * fc_FreePageBtreeFindRightSibling(char *fc_base, FreePageBtree *fc_btp)
{
	FreePageBtree *fc_p = fc_btp;
	int			fc_levels = 0;

	/* 向上移动直到我们能够向右移动。 */
	for (;;)
	{
		Size		fc_first_page;
		Size		fc_index;

		fc_first_page = fc_FreePageBtreeFirstKey(fc_p);
		fc_p = relptr_access(fc_base, fc_p->hdr.parent);

		if (fc_p == NULL)
			return NULL;		/* 我们传入的是最右侧的页面 */

		fc_index = fc_FreePageBtreeSearchInternal(fc_p, fc_first_page);
		if (fc_index < fc_p->hdr.nused - 1)
		{
			Assert(fc_p->u.internal_key[fc_index].first_page == fc_first_page);
			fc_p = relptr_access(fc_base, fc_p->u.internal_key[fc_index + 1].child);
			break;
		}
		Assert(fc_index == fc_p->hdr.nused - 1);
		++fc_levels;
	}

	/* 向左下降。 */
	while (fc_levels > 0)
	{
		Assert(fc_p->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
		fc_p = relptr_access(fc_base, fc_p->u.internal_key[0].child);
		--fc_levels;
	}
	Assert(fc_p->hdr.magic == fc_btp->hdr.magic);

	return fc_p;
}

/*
 * 获取 B 树页面上的第一个键。
 */
static Size fc_FreePageBtreeFirstKey(FreePageBtree *fc_btp)
{
	Assert(fc_btp->hdr.nused > 0);

	if (fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC)
		return fc_btp->u.leaf_key[0].first_page;
	else
	{
		Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
		return fc_btp->u.internal_key[0].first_page;
	}
}

/*
 * 从 B 树回收列表中获取一个页面作为 B 树页面使用。
 */
static FreePageBtree * fc_FreePageBtreeGetRecycled(FreePageManager *fc_fpm)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageSpanLeader *fc_victim = relptr_access(fc_base, fc_fpm->btree_recycle);
	FreePageSpanLeader *fc_newhead;

	Assert(fc_victim != NULL);
	fc_newhead = relptr_access(fc_base, fc_victim->next);
	if (fc_newhead != NULL)
		relptr_copy(fc_newhead->prev, fc_victim->prev);
	relptr_store(fc_base, fc_fpm->btree_recycle, fc_newhead);
	Assert(fpm_pointer_is_page_aligned(fc_base, fc_victim));
	fc_fpm->btree_recycle_count--;
	return (FreePageBtree *) fc_victim;
}

/*
 * 将一个项目插入到内部页面中。
 */
static void fc_FreePageBtreeInsertInternal(char *fc_base, FreePageBtree *fc_btp, Size fc_index,
							Size fc_first_page, FreePageBtree *fc_child)
{
	Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
	Assert(fc_btp->hdr.nused <= FPM_ITEMS_PER_INTERNAL_PAGE);
	Assert(fc_index <= fc_btp->hdr.nused);
	memmove(&fc_btp->u.internal_key[fc_index + 1], &fc_btp->u.internal_key[fc_index],
			sizeof(FreePageBtreeInternalKey) * (fc_btp->hdr.nused - fc_index));
	fc_btp->u.internal_key[fc_index].first_page = fc_first_page;
	relptr_store(fc_base, fc_btp->u.internal_key[fc_index].child, fc_child);
	++fc_btp->hdr.nused;
}

/*
 * 将一个项目插入到叶子页面中。
 */
static void fc_FreePageBtreeInsertLeaf(FreePageBtree *fc_btp, Size fc_index, Size fc_first_page,
						Size fc_npages)
{
	Assert(fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC);
	Assert(fc_btp->hdr.nused <= FPM_ITEMS_PER_LEAF_PAGE);
	Assert(fc_index <= fc_btp->hdr.nused);
	memmove(&fc_btp->u.leaf_key[fc_index + 1], &fc_btp->u.leaf_key[fc_index],
			sizeof(FreePageBtreeLeafKey) * (fc_btp->hdr.nused - fc_index));
	fc_btp->u.leaf_key[fc_index].first_page = fc_first_page;
	fc_btp->u.leaf_key[fc_index].npages = fc_npages;
	++fc_btp->hdr.nused;
}

/*
 * 将一个页面放到 B 树回收列表中。
 */
static void fc_FreePageBtreeRecycle(FreePageManager *fc_fpm, Size fc_pageno)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageSpanLeader *fc_head = relptr_access(fc_base, fc_fpm->btree_recycle);
	FreePageSpanLeader *fc_span;

	fc_span = (FreePageSpanLeader *) fpm_page_to_pointer(fc_base, fc_pageno);
	fc_span->magic = FREE_PAGE_SPAN_LEADER_MAGIC;
	fc_span->npages = 1;
	relptr_store(fc_base, fc_span->next, fc_head);
	relptr_store(fc_base, fc_span->prev, (FreePageSpanLeader *) NULL);
	if (fc_head != NULL)
		relptr_store(fc_base, fc_head->prev, fc_span);
	relptr_store(fc_base, fc_fpm->btree_recycle, fc_span);
	fc_fpm->btree_recycle_count++;
}

/*
 * 从给定页面上的给定位置中移除 B 树中的一个项目。
 */
static void fc_FreePageBtreeRemove(FreePageManager *fc_fpm, FreePageBtree *fc_btp, Size fc_index)
{
	Assert(fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC);
	Assert(fc_index < fc_btp->hdr.nused);

	/* 当最后一个项目被移除时，从 B 树中删除整个页面。 */
	if (fc_btp->hdr.nused == 1)
	{
		fc_FreePageBtreeRemovePage(fc_fpm, fc_btp);
		return;
	}

	/* 从页面中物理移除键。 */
	--fc_btp->hdr.nused;
	if (fc_index < fc_btp->hdr.nused)
		memmove(&fc_btp->u.leaf_key[fc_index], &fc_btp->u.leaf_key[fc_index + 1],
				sizeof(FreePageBtreeLeafKey) * (fc_btp->hdr.nused - fc_index));

	/* 如果我们刚刚移除了第一个键，则调整祖先键。 */
	if (fc_index == 0)
		fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_btp);

	/* 考虑是否将此页面与兄弟页面合并。 */
	fc_FreePageBtreeConsolidate(fc_fpm, fc_btp);
}

/*
 * 从btree中移除一个页面。调用者负责已将此页面中仍需要的任何键重新定位。该页面被放置在回收列表上。
 */
static void fc_FreePageBtreeRemovePage(FreePageManager *fc_fpm, FreePageBtree *fc_btp)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageBtree *fc_parent;
	Size		fc_index;
	Size		fc_first_page;

	for (;;)
	{
		/* 查找父页面。 */
		fc_parent = relptr_access(fc_base, fc_btp->hdr.parent);
		if (fc_parent == NULL)
		{
			/* 我们正在移除根页面。 */
			relptr_store(fc_base, fc_fpm->btree_root, (FreePageBtree *) NULL);
			fc_fpm->btree_depth = 0;
			Assert(fc_fpm->singleton_first_page == 0);
			Assert(fc_fpm->singleton_npages == 0);
			return;
		}

		/*
		 * 如果父页面仅包含一个项目，我们也需要将其移除。
		 */
		if (fc_parent->hdr.nused > 1)
			break;
		fc_FreePageBtreeRecycle(fc_fpm, fpm_pointer_to_page(fc_base, fc_btp));
		fc_btp = fc_parent;
	}

	/* 查找并移除下连接。 */
	fc_first_page = fc_FreePageBtreeFirstKey(fc_btp);
	if (fc_parent->hdr.magic == FREE_PAGE_LEAF_MAGIC)
	{
		fc_index = fc_FreePageBtreeSearchLeaf(fc_parent, fc_first_page);
		Assert(fc_index < fc_parent->hdr.nused);
		if (fc_index < fc_parent->hdr.nused - 1)
			memmove(&fc_parent->u.leaf_key[fc_index],
					&fc_parent->u.leaf_key[fc_index + 1],
					sizeof(FreePageBtreeLeafKey)
					* (fc_parent->hdr.nused - fc_index - 1));
	}
	else
	{
		fc_index = fc_FreePageBtreeSearchInternal(fc_parent, fc_first_page);
		Assert(fc_index < fc_parent->hdr.nused);
		if (fc_index < fc_parent->hdr.nused - 1)
			memmove(&fc_parent->u.internal_key[fc_index],
					&fc_parent->u.internal_key[fc_index + 1],
					sizeof(FreePageBtreeInternalKey)
					* (fc_parent->hdr.nused - fc_index - 1));
	}
	fc_parent->hdr.nused--;
	Assert(fc_parent->hdr.nused > 0);

	/* 回收页面。 */
	fc_FreePageBtreeRecycle(fc_fpm, fpm_pointer_to_page(fc_base, fc_btp));

	/* 如有需要，调整祖先键。 */
	if (fc_index == 0)
		fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_parent);

	/* 考虑是否将父页面与兄弟页面合并。 */
	fc_FreePageBtreeConsolidate(fc_fpm, fc_parent);
}

/*
 * 在btree中搜索给定第一个页面的条目，并用搜索结果初始化
 * *result。result->page和result->index
 * 表示精确匹配的位置或新键应插入的位置。result->found对于精确匹配为真，
 * 否则为假。result->split_pages将包含在执行分割以插入一个键时所需的额外
 * btree页面的数量。除上述描述外，返回时结果对象中字段的内容是未定义的。
 */
static void fc_FreePageBtreeSearch(FreePageManager *fc_fpm, Size fc_first_page,
					FreePageBtreeSearchResult *fc_result)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageBtree *fc_btp = relptr_access(fc_base, fc_fpm->btree_root);
	Size		fc_index;

	fc_result->split_pages = 1;

	/* 如果btree为空，则没有要查找的内容。 */
	if (fc_btp == NULL)
	{
		fc_result->page = NULL;
		fc_result->found = false;
		return;
	}

	/* 向下遍历，直到我们到达叶子。 */
	while (fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC)
	{
		FreePageBtree *fc_child;
		bool		fc_found_exact;

		fc_index = fc_FreePageBtreeSearchInternal(fc_btp, fc_first_page);
		fc_found_exact = fc_index < fc_btp->hdr.nused &&
			fc_btp->u.internal_key[fc_index].first_page == fc_first_page;

		/*
		 * 如果我们找到了精确匹配，则直接向下遍历。否则，
		 * 如果可能，我们向左的子页面下钻，以便可以在该子页面的高端找到
		 * 插入点。
		 */
		if (!fc_found_exact && fc_index > 0)
			--fc_index;

		/* 跟踪叶子插入所需的分割深度。 */
		if (fc_btp->hdr.nused >= FPM_ITEMS_PER_INTERNAL_PAGE)
		{
			Assert(fc_btp->hdr.nused == FPM_ITEMS_PER_INTERNAL_PAGE);
			fc_result->split_pages++;
		}
		else
			fc_result->split_pages = 0;

		/* 下钻到适当的子页面。 */
		Assert(fc_index < fc_btp->hdr.nused);
		fc_child = relptr_access(fc_base, fc_btp->u.internal_key[fc_index].child);
		Assert(relptr_access(fc_base, fc_child->hdr.parent) == fc_btp);
		fc_btp = fc_child;
	}

	/* 跟踪叶子插入所需的分割深度。 */
	if (fc_btp->hdr.nused >= FPM_ITEMS_PER_LEAF_PAGE)
	{
		Assert(fc_btp->hdr.nused == FPM_ITEMS_PER_INTERNAL_PAGE);
		fc_result->split_pages++;
	}
	else
		fc_result->split_pages = 0;

	/* 搜索叶子页面。 */
	fc_index = fc_FreePageBtreeSearchLeaf(fc_btp, fc_first_page);

	/* 整理结果。 */
	fc_result->page = fc_btp;
	fc_result->index = fc_index;
	fc_result->found = fc_index < fc_btp->hdr.nused &&
		fc_first_page == fc_btp->u.leaf_key[fc_index].first_page;
}

/*
 * 在内部页面上搜索第一个大于或等于给定页面编号的键。返回该键的索引，
 * 或如果没有键，则返回大于页面上键的数量的一个。
 */
static Size fc_FreePageBtreeSearchInternal(FreePageBtree *fc_btp, Size fc_first_page)
{
	Size		fc_low = 0;
	Size		fc_high = fc_btp->hdr.nused;

	Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
	Assert(fc_high > 0 && fc_high <= FPM_ITEMS_PER_INTERNAL_PAGE);

	while (fc_low < fc_high)
	{
		Size		fc_mid = (fc_low + fc_high) / 2;
		Size		fc_val = fc_btp->u.internal_key[fc_mid].first_page;

		if (fc_first_page == fc_val)
			return fc_mid;
		else if (fc_first_page < fc_val)
			fc_high = fc_mid;
		else
			fc_low = fc_mid + 1;
	}

	return fc_low;
}

/*
 * 在叶子页面上搜索第一个大于或等于给定页面编号的键。返回该键的索引，
 * 或如果没有键，则返回大于页面上键的数量的一个。
 */
static Size fc_FreePageBtreeSearchLeaf(FreePageBtree *fc_btp, Size fc_first_page)
{
	Size		fc_low = 0;
	Size		fc_high = fc_btp->hdr.nused;

	Assert(fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC);
	Assert(fc_high > 0 && fc_high <= FPM_ITEMS_PER_LEAF_PAGE);

	while (fc_low < fc_high)
	{
		Size		fc_mid = (fc_low + fc_high) / 2;
		Size		fc_val = fc_btp->u.leaf_key[fc_mid].first_page;

		if (fc_first_page == fc_val)
			return fc_mid;
		else if (fc_first_page < fc_val)
			fc_high = fc_mid;
		else
			fc_low = fc_mid + 1;
	}

	return fc_low;
}

/*
 * 分配一个新的btree页面，并将提供页面中的一半键
 * 移动至新页面。调用者负责确保fpm->btree_recycle中有一个页面可用。
 * 返回指向新页面的指针，调用者必须添加一个下连接。
 */
static FreePageBtree * fc_FreePageBtreeSplitPage(FreePageManager *fc_fpm, FreePageBtree *fc_btp)
{
	FreePageBtree *fc_newsibling;

	fc_newsibling = fc_FreePageBtreeGetRecycled(fc_fpm);
	fc_newsibling->hdr.magic = fc_btp->hdr.magic;
	fc_newsibling->hdr.nused = fc_btp->hdr.nused / 2;
	relptr_copy(fc_newsibling->hdr.parent, fc_btp->hdr.parent);
	fc_btp->hdr.nused -= fc_newsibling->hdr.nused;

	if (fc_btp->hdr.magic == FREE_PAGE_LEAF_MAGIC)
		memcpy(&fc_newsibling->u.leaf_key,
			   &fc_btp->u.leaf_key[fc_btp->hdr.nused],
			   sizeof(FreePageBtreeLeafKey) * fc_newsibling->hdr.nused);
	else
	{
		Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
		memcpy(&fc_newsibling->u.internal_key,
			   &fc_btp->u.internal_key[fc_btp->hdr.nused],
			   sizeof(FreePageBtreeInternalKey) * fc_newsibling->hdr.nused);
		fc_FreePageBtreeUpdateParentPointers(fpm_segment_base(fc_fpm), fc_newsibling);
	}

	return fc_newsibling;
}

/*
 * 当内部页面被拆分或合并时，必须更新其
 * 子页面的父指针。
 */
static void fc_FreePageBtreeUpdateParentPointers(char *fc_base, FreePageBtree *fc_btp)
{
	Size		fc_i;

	Assert(fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC);
	for (fc_i = 0; fc_i < fc_btp->hdr.nused; ++fc_i)
	{
		FreePageBtree *fc_child;

		fc_child = relptr_access(fc_base, fc_btp->u.internal_key[fc_i].child);
		relptr_store(fc_base, fc_child->hdr.parent, fc_btp);
	}
}

/*
 * btree数据的调试转储。
 */
static void fc_FreePageManagerDumpBtree(FreePageManager *fc_fpm, FreePageBtree *fc_btp,
						 FreePageBtree *fc_parent, int fc_level, StringInfo fc_buf)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	Size		fc_pageno = fpm_pointer_to_page(fc_base, fc_btp);
	Size		fc_index;
	FreePageBtree *fc_check_parent;

	check_stack_depth();
	fc_check_parent = relptr_access(fc_base, fc_btp->hdr.parent);
	appendStringInfo(fc_buf, "  %zu@%d %c", fc_pageno, fc_level,
					 fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC ? 'i' : 'l');
	if (fc_parent != fc_check_parent)
		appendStringInfo(fc_buf, " [actual parent %zu, expected %zu]",
						 fpm_pointer_to_page(fc_base, fc_check_parent),
						 fpm_pointer_to_page(fc_base, fc_parent));
	appendStringInfoChar(fc_buf, ':');
	for (fc_index = 0; fc_index < fc_btp->hdr.nused; ++fc_index)
	{
		if (fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC)
			appendStringInfo(fc_buf, " %zu->%zu",
							 fc_btp->u.internal_key[fc_index].first_page,
							 relptr_offset(fc_btp->u.internal_key[fc_index].child) / FPM_PAGE_SIZE);
		else
			appendStringInfo(fc_buf, " %zu(%zu)",
							 fc_btp->u.leaf_key[fc_index].first_page,
							 fc_btp->u.leaf_key[fc_index].npages);
	}
	appendStringInfoChar(fc_buf, '\n');

	if (fc_btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC)
	{
		for (fc_index = 0; fc_index < fc_btp->hdr.nused; ++fc_index)
		{
			FreePageBtree *fc_child;

			fc_child = relptr_access(fc_base, fc_btp->u.internal_key[fc_index].child);
			fc_FreePageManagerDumpBtree(fc_fpm, fc_child, fc_btp, fc_level + 1, fc_buf);
		}
	}
}

/*
 * 空闲跨度数据的调试转储。
 */
static void fc_FreePageManagerDumpSpans(FreePageManager *fc_fpm, FreePageSpanLeader *fc_span,
						 Size fc_expected_pages, StringInfo fc_buf)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);

	while (fc_span != NULL)
	{
		if (fc_span->npages != fc_expected_pages)
			appendStringInfo(fc_buf, " %zu(%zu)", fpm_pointer_to_page(fc_base, fc_span),
							 fc_span->npages);
		else
			appendStringInfo(fc_buf, " %zu", fpm_pointer_to_page(fc_base, fc_span));
		fc_span = relptr_access(fc_base, fc_span->next);
	}

	appendStringInfoChar(fc_buf, '\n');
}

/*
 * 此函数从自由页面管理器中分配给定长度的一组页面。
 */
static bool fc_FreePageManagerGetInternal(FreePageManager *fc_fpm, Size fc_npages, Size *fc_first_page)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageSpanLeader *fc_victim = NULL;
	FreePageSpanLeader *fc_prev;
	FreePageSpanLeader *fc_next;
	FreePageBtreeSearchResult fc_result;
	Size		fc_victim_page = 0;	/* 安抚编译器 */
	Size		fc_f;

	/*
	 * 搜索一个空闲跨度。
	 *
	 * 现在，我们在这里使用简单的最佳适应策略，但这可能会导致内存碎片，
	 * 如果我们一再要求分配的块仅比我们可用的稍小。希望这不太可能，
	 * 因为我们预计大多数请求是单个页面或超级块大小的块——但是没有政策
	 * 可以在所有情况下都是最优的，除非它对未来的分配模式有了解。
	 */
	for (fc_f = Min(fc_npages, FPM_NUM_FREELISTS) - 1; fc_f < FPM_NUM_FREELISTS; ++fc_f)
	{
		/* 跳过空的空闲列表。 */
		if (relptr_is_null(fc_fpm->freelist[fc_f]))
			continue;

		/*
		 * 除了最后一个之外，所有空闲列表仅包含单一大小的项目，
		 * 所以我们只需采用第一个。但最后一个空闲
		 * 列表包含任何其他列表中太大的所有内容，因此我们
		 * 需要搜索该列表。
		 */
		if (fc_f < FPM_NUM_FREELISTS - 1)
			fc_victim = relptr_access(fc_base, fc_fpm->freelist[fc_f]);
		else
		{
			FreePageSpanLeader *fc_candidate;

			fc_candidate = relptr_access(fc_base, fc_fpm->freelist[fc_f]);
			do
			{
				if (fc_candidate->npages >= fc_npages && (fc_victim == NULL ||
													fc_victim->npages > fc_candidate->npages))
				{
					fc_victim = fc_candidate;
					if (fc_victim->npages == fc_npages)
						break;
				}
				fc_candidate = relptr_access(fc_base, fc_candidate->next);
			} while (fc_candidate != NULL);
		}
		break;
	}

	/* 如果我们没找到可分配的跨度，返回失败。 */
	if (fc_victim == NULL)
		return false;

	/* 从空闲列表中移除跨度。 */
	Assert(fc_victim->magic == FREE_PAGE_SPAN_LEADER_MAGIC);
	fc_prev = relptr_access(fc_base, fc_victim->prev);
	fc_next = relptr_access(fc_base, fc_victim->next);
	if (fc_prev != NULL)
		relptr_copy(fc_prev->next, fc_victim->next);
	else
		relptr_copy(fc_fpm->freelist[fc_f], fc_victim->next);
	if (fc_next != NULL)
		relptr_copy(fc_next->prev, fc_victim->prev);
	fc_victim_page = fpm_pointer_to_page(fc_base, fc_victim);

	/* 决定我们是否可能使连续页面失效。 */
	if (fc_f == FPM_NUM_FREELISTS - 1 &&
		fc_victim->npages == fc_fpm->contiguous_pages)
	{
		/*
		 * 受害者跨度来自于超大空闲列表，并且与
		 * 最长跨度的大小相同。可能有或可能没有另一个相同大小的，
		 * 因此必须重新计算连续页面以确保安全。
		 */
		fc_fpm->contiguous_pages_dirty = true;
	}
	else if (fc_f + 1 == fc_fpm->contiguous_pages &&
			 relptr_is_null(fc_fpm->freelist[fc_f]))
	{
		/*
		 * 受害者跨度来自固定大小的自由列表，它是当前最长跨度大小相同的列表，
		 * 在移除受害者后，该列表现在为空。因此，必须毫无疑问地重新计算 contiguous_pages。
		 */
		fc_fpm->contiguous_pages_dirty = true;
	}

	/*
	 * 如果我们尚未初始化 btree，受害者必须是 FreePageManager 本身存储的唯一跨度。
	 * 否则，我们需要更新 btree。
	 */
	if (relptr_is_null(fc_fpm->btree_root))
	{
		Assert(fc_victim_page == fc_fpm->singleton_first_page);
		Assert(fc_victim->npages == fc_fpm->singleton_npages);
		Assert(fc_victim->npages >= fc_npages);
		fc_fpm->singleton_first_page += fc_npages;
		fc_fpm->singleton_npages -= fc_npages;
		if (fc_fpm->singleton_npages > 0)
			fc_FreePagePushSpanLeader(fc_fpm, fc_fpm->singleton_first_page,
								   fc_fpm->singleton_npages);
	}
	else
	{
		/*
		 * 如果我们找到的跨度恰好是合适的大小，完全从 btree 中移除它。
		 * 否则，调整 btree 条目以反映跨度中仍未分配的部分，并将该部分放入适当的自由列表中。
		 */
		fc_FreePageBtreeSearch(fc_fpm, fc_victim_page, &fc_result);
		Assert(fc_result.found);
		if (fc_victim->npages == fc_npages)
			fc_FreePageBtreeRemove(fc_fpm, fc_result.page, fc_result.index);
		else
		{
			FreePageBtreeLeafKey *fc_key;

			/* 调整 btree 以反映剩余页面。 */
			Assert(fc_victim->npages > fc_npages);
			fc_key = &fc_result.page->u.leaf_key[fc_result.index];
			Assert(fc_key->npages == fc_victim->npages);
			fc_key->first_page += fc_npages;
			fc_key->npages -= fc_npages;
			if (fc_result.index == 0)
				fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_result.page);

			/* 将未分配的页面放回适当的自由列表。 */
			fc_FreePagePushSpanLeader(fc_fpm, fc_victim_page + fc_npages,
								   fc_victim->npages - fc_npages);
		}
	}

	/* 将结果返回给调用者。 */
	*fc_first_page = fpm_pointer_to_page(fc_base, fc_victim);
	return true;
}

/*
 * 将一个页面范围放入 btree 和自由列表，将其与其前后现有的自由跨度合并。
 * 如果 'soft' 为真，仅在可以不分配新的 btree 页面时执行插入；如果为 false，则始终执行。
 * 如果软标志导致插入被跳过，则返回 0，否则返回由于插入创建的连续跨度的大小。
 * 如果我们能够与相邻范围合并，这可能大于 npages。
 */
static Size fc_FreePageManagerPutInternal(FreePageManager *fc_fpm, Size fc_first_page, Size fc_npages,
						   bool fc_soft)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageBtreeSearchResult fc_result;
	FreePageBtreeLeafKey *fc_prevkey = NULL;
	FreePageBtreeLeafKey *fc_nextkey = NULL;
	FreePageBtree *fc_np;
	Size		fc_nindex;

	Assert(fc_npages > 0);

	/* 我们可以在不初始化 btree 的情况下存储一个单一的自由跨度。 */
	if (fc_fpm->btree_depth == 0)
	{
		if (fc_fpm->singleton_npages == 0)
		{
			/* 还没有跨度；存储这个。 */
			fc_fpm->singleton_first_page = fc_first_page;
			fc_fpm->singleton_npages = fc_npages;
			fc_FreePagePushSpanLeader(fc_fpm, fc_first_page, fc_npages);
			return fc_fpm->singleton_npages;
		}
		else if (fc_fpm->singleton_first_page + fc_fpm->singleton_npages ==
				 fc_first_page)
		{
			/* 新跨度紧接在唯一现有跨度之后。 */
			fc_fpm->singleton_npages += fc_npages;
			fc_FreePagePopSpanLeader(fc_fpm, fc_fpm->singleton_first_page);
			fc_FreePagePushSpanLeader(fc_fpm, fc_fpm->singleton_first_page,
								   fc_fpm->singleton_npages);
			return fc_fpm->singleton_npages;
		}
		else if (fc_first_page + fc_npages == fc_fpm->singleton_first_page)
		{
			/* 新跨度紧接在唯一现有跨度之前。 */
			fc_FreePagePopSpanLeader(fc_fpm, fc_fpm->singleton_first_page);
			fc_fpm->singleton_first_page = fc_first_page;
			fc_fpm->singleton_npages += fc_npages;
			fc_FreePagePushSpanLeader(fc_fpm, fc_fpm->singleton_first_page,
								   fc_fpm->singleton_npages);
			return fc_fpm->singleton_npages;
		}
		else
		{
			/* 不连续；我们需要初始化 btree。 */
			Size		fc_root_page;
			FreePageBtree *fc_root;

			if (!relptr_is_null(fc_fpm->btree_recycle))
				fc_root = fc_FreePageBtreeGetRecycled(fc_fpm);
			else if (fc_soft)
				return 0;		/* 如果是软插入，应该不分配。 */
			else if (fc_FreePageManagerGetInternal(fc_fpm, 1, &fc_root_page))
				fc_root = (FreePageBtree *) fpm_page_to_pointer(fc_base, fc_root_page);
			else
			{
				/* 我们最好从现有范围中获取页面。 */
				elog(FATAL, "free page manager btree is corrupt");
			}

			/* 创建 btree 并将预先存在的范围移动到其中。 */
			fc_root->hdr.magic = FREE_PAGE_LEAF_MAGIC;
			fc_root->hdr.nused = 1;
			relptr_store(fc_base, fc_root->hdr.parent, (FreePageBtree *) NULL);
			fc_root->u.leaf_key[0].first_page = fc_fpm->singleton_first_page;
			fc_root->u.leaf_key[0].npages = fc_fpm->singleton_npages;
			relptr_store(fc_base, fc_fpm->btree_root, fc_root);
			fc_fpm->singleton_first_page = 0;
			fc_fpm->singleton_npages = 0;
			fc_fpm->btree_depth = 1;

			/*
			 * 边界情况：可能是 btree 树根占用了最后一个
			 * 空闲页面。在这种情况下，唯一的 btree 条目覆盖一个零
			 * 页面运行，这是无效的。用我们尝试插入的条目覆盖它并退出。
			 */
			if (fc_root->u.leaf_key[0].npages == 0)
			{
				fc_root->u.leaf_key[0].first_page = fc_first_page;
				fc_root->u.leaf_key[0].npages = fc_npages;
				fc_FreePagePushSpanLeader(fc_fpm, fc_first_page, fc_npages);
				return fc_npages;
			}

			/* 继续插入新键。 */
		}
	}

	/* 搜索 btree。 */
	fc_FreePageBtreeSearch(fc_fpm, fc_first_page, &fc_result);
	Assert(!fc_result.found);
	if (fc_result.index > 0)
		fc_prevkey = &fc_result.page->u.leaf_key[fc_result.index - 1];
	if (fc_result.index < fc_result.page->hdr.nused)
	{
		fc_np = fc_result.page;
		fc_nindex = fc_result.index;
		fc_nextkey = &fc_result.page->u.leaf_key[fc_result.index];
	}
	else
	{
		fc_np = fc_FreePageBtreeFindRightSibling(fc_base, fc_result.page);
		fc_nindex = 0;
		if (fc_np != NULL)
			fc_nextkey = &fc_np->u.leaf_key[0];
	}

	/* 如果可能，与前一条目合并。 */
	if (fc_prevkey != NULL && fc_prevkey->first_page + fc_prevkey->npages >= fc_first_page)
	{
		bool		fc_remove_next = false;
		Size		fc_result;

		Assert(fc_prevkey->first_page + fc_prevkey->npages == fc_first_page);
		fc_prevkey->npages = (fc_first_page - fc_prevkey->first_page) + fc_npages;

		/* 检查我们是否也可以与后续条目合并。 */
		if (fc_nextkey != NULL &&
			fc_prevkey->first_page + fc_prevkey->npages >= fc_nextkey->first_page)
		{
			Assert(fc_prevkey->first_page + fc_prevkey->npages ==
				   fc_nextkey->first_page);
			fc_prevkey->npages = (fc_nextkey->first_page - fc_prevkey->first_page)
				+ fc_nextkey->npages;
			fc_FreePagePopSpanLeader(fc_fpm, fc_nextkey->first_page);
			fc_remove_next = true;
		}

		/* 将跨度放在正确的自由列表上并保存大小。 */
		fc_FreePagePopSpanLeader(fc_fpm, fc_prevkey->first_page);
		fc_FreePagePushSpanLeader(fc_fpm, fc_prevkey->first_page, fc_prevkey->npages);
		fc_result = fc_prevkey->npages;

		/*
		 * 如果我们与前面的条目和后面的条目合并，
		 * 我们必须移除后面的条目。我们最后这样做，因为
		 * 从 btree 中移除元素可能会使我们持有的
		 * 当前数据结构中的指针无效。
		 *
		 * 注意：此时 btree 在技术上处于无效状态，
		 * 因为我们已经更新了 prevkey 以覆盖与 nextkey 相同的键空间。
		 * FreePageBtreeRemove() 不应该注意到这一点。
		 */
		if (fc_remove_next)
			fc_FreePageBtreeRemove(fc_fpm, fc_np, fc_nindex);

		return fc_result;
	}

	/* 如果可能，与下一个条目合并。 */
	if (fc_nextkey != NULL && fc_first_page + fc_npages >= fc_nextkey->first_page)
	{
		Size		fc_newpages;

		/* 计算跨度的新大小。 */
		Assert(fc_first_page + fc_npages == fc_nextkey->first_page);
		fc_newpages = (fc_nextkey->first_page - fc_first_page) + fc_nextkey->npages;

		/* 将跨度放在正确的自由列表上。 */
		fc_FreePagePopSpanLeader(fc_fpm, fc_nextkey->first_page);
		fc_FreePagePushSpanLeader(fc_fpm, fc_first_page, fc_newpages);

		/* 就地更新键。 */
		fc_nextkey->first_page = fc_first_page;
		fc_nextkey->npages = fc_newpages;

		/* 如果减少了页面上的第一个键，祖先可能需要调整。 */
		if (fc_nindex == 0)
			fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_np);

		return fc_nextkey->npages;
	}

	/* 拆分叶页面及其必要的祖先。 */
	if (fc_result.split_pages > 0)
	{
		/*
		 * 注意：我们可以考虑各种应对策略以避免拆分；
		 * 最明显的是，如果 np != result.page，我们可以针对该
		 * 页面。更复杂的重新排序策略也可能是可能的；
		 * 基本上，除非每个叶页面都 100% 满，否则如果我们努力，
		 * 可以将这个键插入进去。努力尝试的可能性不大，但我们
		 * 可能需要做比无所作为更多的努力。现在，我们只是做
		 * 轻松的事情，也就是不做任何事情。
		 */

		/* 如果这是一个软插入，现在是放弃的时候。 */
		if (fc_soft)
			return 0;

		
/* 检查我们是否需要分配更多的btree页面以进行分割。 */
		if (fc_result.split_pages > fc_fpm->btree_recycle_count)
		{
			Size		fc_pages_needed;
			Size		fc_recycle_page;
			Size		fc_i;

			/*
			 * 分配所需数量的页面并逐一进行分割。这不应该失败，
			 * 因为如果我们有足够的可用页面范围，而我们需要额外的存储空间
			 * 来记住它们，那么我们肯定应该有足够的空间来扩展btree，
			 * 它所使用的页面数量相对于管理页面的数量应该只是微不足道的。
			 * 如果发生这样的情况，那么一定是系统出现了严重的问题。
			 */
			fc_pages_needed = fc_result.split_pages - fc_fpm->btree_recycle_count;
			for (fc_i = 0; fc_i < fc_pages_needed; ++fc_i)
			{
				if (!fc_FreePageManagerGetInternal(fc_fpm, 1, &fc_recycle_page))
					elog(FATAL, "free page manager btree is corrupt");
				fc_FreePageBtreeRecycle(fc_fpm, fc_recycle_page);
			}

			/*
			 * 分配页面以回收的行为可能使我们之前的btree研究结果失效，
			 * 所以要重复这个过程。我们可以重新检查一下之前不切实际的
			 * 任何避免分割的策略现在是否可行，但这似乎没什么意义，
			 * 所以我们就不去做了。现在如果之前无法聚合，那么现在也不可能。
			 */
			fc_FreePageBtreeSearch(fc_fpm, fc_first_page, &fc_result);

			/*
			 * 为构建我们的btree而分配页面的行为不应该导致任何页面变得更满，
			 * 因此新的分割深度不应该大于旧的深度，如果我们幸运地分配了
			 * 一块释放了我们需要更新的页面上的一个位置，那么可能会更少。
			 */
			Assert(fc_result.split_pages <= fc_fpm->btree_recycle_count);
		}

		/* 如果我们仍然需要进行分割，就进行分割。 */
		if (fc_result.split_pages > 0)
		{
			FreePageBtree *fc_split_target = fc_result.page;
			FreePageBtree *fc_child = NULL;
			Size		fc_key = fc_first_page;

			for (;;)
			{
				FreePageBtree *fc_newsibling;
				FreePageBtree *fc_parent;

				/* 确定父页面，它必须接收下行链接。 */
				fc_parent = relptr_access(fc_base, fc_split_target->hdr.parent);

				/* 分割页面 - 下行链接尚未添加。 */
				fc_newsibling = fc_FreePageBtreeSplitPage(fc_fpm, fc_split_target);

				/*
				 * 在循环的这一点上，我们总是携带一个待定的插入。在第一次
				 * 迭代中，它是我们尝试插入的实际键；在后续的迭代中，它是
				 * 由于前一轮循环迭代中进行的分割而需要添加的下行链接。
				 * 由于我们刚刚分割了页面，因此在两个结果页面中的一个上
				 * 肯定还有空间。
				 */
				if (fc_child == NULL)
				{
					Size		fc_index;
					FreePageBtree *insert_into;

					insert_into = fc_key < fc_newsibling->u.leaf_key[0].first_page ?
						fc_split_target : fc_newsibling;
					fc_index = fc_FreePageBtreeSearchLeaf(insert_into, fc_key);
					fc_FreePageBtreeInsertLeaf(insert_into, fc_index, fc_key, fc_npages);
					if (fc_index == 0 && insert_into == fc_split_target)
						fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_split_target);
				}
				else
				{
					Size		fc_index;
					FreePageBtree *insert_into;

					insert_into =
						fc_key < fc_newsibling->u.internal_key[0].first_page ?
						fc_split_target : fc_newsibling;
					fc_index = fc_FreePageBtreeSearchInternal(insert_into, fc_key);
					fc_FreePageBtreeInsertInternal(fc_base, insert_into, fc_index,
												fc_key, fc_child);
					relptr_store(fc_base, fc_child->hdr.parent, insert_into);
					if (fc_index == 0 && insert_into == fc_split_target)
						fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_split_target);
				}

				/* 如果我们刚刚分割的页面没有父页面，分割根节点。 */
				if (fc_parent == NULL)
				{
					FreePageBtree *fc_newroot;

					fc_newroot = fc_FreePageBtreeGetRecycled(fc_fpm);
					fc_newroot->hdr.magic = FREE_PAGE_INTERNAL_MAGIC;
					fc_newroot->hdr.nused = 2;
					relptr_store(fc_base, fc_newroot->hdr.parent,
								 (FreePageBtree *) NULL);
					fc_newroot->u.internal_key[0].first_page =
						fc_FreePageBtreeFirstKey(fc_split_target);
					relptr_store(fc_base, fc_newroot->u.internal_key[0].child,
								 fc_split_target);
					relptr_store(fc_base, fc_split_target->hdr.parent, fc_newroot);
					fc_newroot->u.internal_key[1].first_page =
						fc_FreePageBtreeFirstKey(fc_newsibling);
					relptr_store(fc_base, fc_newroot->u.internal_key[1].child,
								 fc_newsibling);
					relptr_store(fc_base, fc_newsibling->hdr.parent, fc_newroot);
					relptr_store(fc_base, fc_fpm->btree_root, fc_newroot);
					fc_fpm->btree_depth++;

					break;
				}

				/* 如果父页面没有满，插入下行链接。 */
				fc_key = fc_newsibling->u.internal_key[0].first_page;
				if (fc_parent->hdr.nused < FPM_ITEMS_PER_INTERNAL_PAGE)
				{
					Size		fc_index;

					fc_index = fc_FreePageBtreeSearchInternal(fc_parent, fc_key);
					fc_FreePageBtreeInsertInternal(fc_base, fc_parent, fc_index,
												fc_key, fc_newsibling);
					relptr_store(fc_base, fc_newsibling->hdr.parent, fc_parent);
					if (fc_index == 0)
						fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_parent);
					break;
				}

				/* 父页面也需要进行分割，所以循环回去。 */
				fc_child = fc_newsibling;
				fc_split_target = fc_parent;
			}

			/*
			 * 上面的循环完成了插入，所以只需要更新空闲列表，完成操作。
			 */
			fc_FreePagePushSpanLeader(fc_fpm, fc_first_page, fc_npages);

			return fc_npages;
		}
	}

	/* 物理上将键添加到页面。 */
	Assert(fc_result.page->hdr.nused < FPM_ITEMS_PER_LEAF_PAGE);
	fc_FreePageBtreeInsertLeaf(fc_result.page, fc_result.index, fc_first_page, fc_npages);

	/* 如果页面上是新的第一个键，祖先可能需要调整。 */
	if (fc_result.index == 0)
		fc_FreePageBtreeAdjustAncestorKeys(fc_fpm, fc_result.page);

	/* 将其放入空闲列表。 */
	fc_FreePagePushSpanLeader(fc_fpm, fc_first_page, fc_npages);

	return fc_npages;
}

/*
 * 从包含它的链表中移除一个FreePageSpanLeader，可能是因为我们正在更改
 * 脚本的大小，或者因为我们正在分配它。
 */
static void fc_FreePagePopSpanLeader(FreePageManager *fc_fpm, Size fc_pageno)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	FreePageSpanLeader *fc_span;
	FreePageSpanLeader *fc_next;
	FreePageSpanLeader *fc_prev;

	fc_span = (FreePageSpanLeader *) fpm_page_to_pointer(fc_base, fc_pageno);

	fc_next = relptr_access(fc_base, fc_span->next);
	fc_prev = relptr_access(fc_base, fc_span->prev);
	if (fc_next != NULL)
		relptr_copy(fc_next->prev, fc_span->prev);
	if (fc_prev != NULL)
		relptr_copy(fc_prev->next, fc_span->next);
	else
	{
		Size		fc_f = Min(fc_span->npages, FPM_NUM_FREELISTS) - 1;

		Assert(relptr_offset(fc_fpm->freelist[fc_f]) == fc_pageno * FPM_PAGE_SIZE);
		relptr_copy(fc_fpm->freelist[fc_f], fc_span->next);
	}
}

/*
 * 初始化一个新的FreePageSpanLeader并将其放入适当的空闲列表中。
 */
static void fc_FreePagePushSpanLeader(FreePageManager *fc_fpm, Size fc_first_page, Size fc_npages)
{
	char	   *fc_base = fpm_segment_base(fc_fpm);
	Size		fc_f = Min(fc_npages, FPM_NUM_FREELISTS) - 1;
	FreePageSpanLeader *fc_head = relptr_access(fc_base, fc_fpm->freelist[fc_f]);
	FreePageSpanLeader *fc_span;

	fc_span = (FreePageSpanLeader *) fpm_page_to_pointer(fc_base, fc_first_page);
	fc_span->magic = FREE_PAGE_SPAN_LEADER_MAGIC;
	fc_span->npages = fc_npages;
	relptr_store(fc_base, fc_span->next, fc_head);
	relptr_store(fc_base, fc_span->prev, (FreePageSpanLeader *) NULL);
	if (fc_head != NULL)
		relptr_store(fc_base, fc_head->prev, fc_span);
	relptr_store(fc_base, fc_fpm->freelist[fc_f], fc_span);
}
